Corelab Seminar
2010-2011
Christos Tzamos (MIT, NTUA)
Mechanism Design Without Money
Abstract.
In this thesis, we consider the problem of Mechanism Design without
Money in the Social Choice setting. Due to the main impossibility result, only
trivial mechanisms are strategyproof for the general setting, so we explore more
restricted domains like single-peaked preferences and metric spaces. We study the problem as a facility
location game, where a number of facilities are to be placed in a metric space based
on locations reported by strategic agents. A mechanism maps theagentsʼ locations
to a set of facilities. Every agent seeks to minimize her connection cost,
namely the distance of her true location to the nearest facility, and
may misreport her location. We are interested in mechanisms that are strategyproof,
i.e., ensure that no agent can benefit from
misreporting her location,
do not resort to monetary transfers, and approximate the optimal social cost.
The mechanisms can be either deterministic or randomized. We provide
upper bounds along with corresponding lower bounds for different cases:
single facility, fixed number of facilities and facilities with
uniform opening cost.